package com.moyoutian.leetcode;

/**
 * 476. 数字的补数
 * <p>
 * 给你一个 正 整数 num ，输出它的补数。补数是对该数的二进制表示取反。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：num = 5
 * <p>
 * 输出：2
 * <p>
 * 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：num = 1
 * <p>
 * 输出：0
 * <p>
 * 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 给定的整数 num 保证在 32 位带符号整数的范围内。
 * <p>
 * num >= 1
 * <p>
 * 你可以假定二进制数不包含前导零位。
 * <p>
 * 本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同
 */
public class Demo476 {
    public static void main(String[] args) {
        int num = 10;
        System.out.println(findComplement(num));
    }

    public static int findComplement(int num) {
        //1111
        //1000
        int n = num;
        //1111>>>1 = 111  , 1111|111=1111
        //1000>>>1 = 100  , 1000|100=1100;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        //n= 最高位开始都是11...
        return n ^ num;
    }
}
